#!/usr/bin/python
# -*- coding: utf-8 -*


maze = [
     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
     [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],  #这是 1,1
     [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
     [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
     [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
     [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
     [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
     [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
     [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
#上右下左
dirs = [
    lambda x,y: (x+1,y),
    lambda x,y: (x-1,y),
    lambda x,y: (x,y-1),
    lambda x,y: (x,y+1)
]

def maze_path(x1,y1,x2,y2):
    #空栈
    stack = []
    stack.append((x1, y1))

    #栈空了就是没有路了
    while(len(stack)>0):
        #当前节点
        curNode = stack[-1]
        if curNode[0] == x2 and curNode[1] == y2:
            #走到终点
            for p in stack:
                print('->', end=' ')
                print(p, end=' ')
            #有路返回true
            return True

        #0是x 1是y
        for dir in dirs:
            #下一个节点
            nextNode = dir(curNode[0],curNode[1])
            #如果下一个节点能走
            if maze[nextNode[0]][nextNode[1]] == 0:
                stack.append(nextNode)
                maze[nextNode[0]][nextNode[1]] = 2 #2表示为已经走过了
                break
        else: #四个方向,没有路了,回退栈
            #标记走过了， 之前走的就不会在走了
            maze[nextNode[0]][nextNode[1]] =2
            #回退，出栈
            stack.pop()
    else:
        print("没有路")
        return False

maze_path(1,1,8,8)
# -> (1, 1) -> (2, 1) -> (3, 1) -> (4, 1) -> (5, 1) -> (5, 2) -> (5, 3) -> (6, 3) -> (6, 4) -> (6, 5) -> (7, 5) -> (8, 5) -> (8, 6) -> (8, 7) -> (8, 8)